package sort;


public class HeapSort{

	public static void main(String[] args) {
		int[] array = {43,52,62,10,40,32,59,100, 23, 15, 15, -5, 100,-5,36,-9,42,57,31,-100,5,4,2,9,15,26};
//		int[] array = {43,52,62,10,40,32,59};
//		int[] array = {9, 12, 17,65,50,20,60,30,4,19};
//		heapSort(array);
		heapSort2(array);
		for (int i : array) {
			System.out.print(i + " ");
		}
	}

	public static void heapSort(int[] array) {
		//首先建立堆,建立大根堆
		//这种建立堆的方式是自底向上的构建堆的方式
		//核心思想就是首先将数组A视为一颗尚未完全满足堆性质的完全二叉树
		//结点数为n的二叉树中，A[ floor(n/2) ], A[ floor(n/2)+ 1] ...A[n - 1] 是完全二叉树的叶子节点，即为单节点堆
		//然后将A[ floor(n/2) - 1]到0自右向左， 自下向上反向层序遍历二叉树的所有非叶子结点
		int i;
		for (i = array.length / 2 - 1; i >= 0; i--){ // 非叶节点最大序号值为size/2 - 1
			heapAdjust2(array, i, array.length);  //对与i为堆顶的元素做筛运算
		}
		for (int j : array) {
			System.out.print(j + " ");
		}
		System.out.println();
		//上筛，从n - 1 到0的顺序上筛
		//迭代操作首先交换最高优先级的元素array[0]与array[i]
		for (i = array.length - 1; i > 0; i--) {
			MaoPaoSort.swap(array, 0, i);  // 交换堆顶和i元素，即每次将剩余元素中的最大者放到最后面
			heapAdjust2(array, 0, i); // 重新调整堆顶节点成为大顶堆
			
			//查看每次调整堆之后整个堆得情况
			System.out.println("第i: " + i + "次调整：" );
			for (int j : array) {
				System.out.print(j + " ");
			}
			System.out.println();
		}
	}
	
	//调整堆，以i结点为跟的左子树和右子树已经为堆 
	//类似于插入排序的将一个数据插入到已经排好序中数组的位置
	public static void heapAdjust(int[] array, int i, int size){
		//注意数组的下标是从0开始的
		int left = 2 * (i + 1) - 1;  //i的左孩子结点序号
		int right = 2 * (i + 1);  //i的右孩子结点序号
		int max = i;
		//如果i是叶结点就不用调整
		if(i <= size/2){
			//找到左右结点中最大的
			if (left < size && array[left] > array[max]) {
				max = left;
			}
			if (right < size&& array[right] > array[max]) {
				max = right;
			}
			//其实上面的这种判断可以写成,不过初始要赋值为left
//			if(right < size - 1 &&  array[right] > array[left]){
//				max = right;
//			}
			if(max != i){
				MaoPaoSort.swap(array, i, max);
				//然后重新调整左子树或者右子树
				heapAdjust(array, max, size);
			}
		}
	}
	
	//需要调整的是i结点  其子结点为i * 2 和 i * 2 + 1 
	public static void heapAdjust2(int[] array, int i, int size){
		int temp = array[i];
		int childPos = (i + 1) * 2 - 1;  //子节点中数据较大的下标，初始为左结点
		if(i <= size/2){
			if(childPos < size - 1 && array[childPos] < array[childPos + 1]){
				//此时右结点的值要大于左结点
				childPos = childPos + 1;
			}
			if(childPos < size && array[childPos] > temp){
				MaoPaoSort.swap(array, i, childPos);
				//然后重新调整左子树或者右子树
				heapAdjust(array, childPos, size);
			}
		}
	}
	
	
	public static void heapSort2(int[] array){
		if(array == null || array.length <= 1){
			return ;
		}
		//首先建立堆，这里采用的是自底向上的方法
		int length = array.length;
		for(int i = length / 2 - 1; i >= 0; i--){
			heapAdjustTest(array, i, length);
		}
		for(int i = length - 1; i > 0; i--){
			MaoPaoSort.swap(array, i, 0);
			heapAdjustTest(array, 0, i);
		}
	}
	
	
	public static void heapAdjustTest(int[] array, int i, int length){
		//叶子结点无需调整
		if(i >= length / 2){
			return;
		}
		//初始为左结点
		int child =  ( i + 1) * 2 - 1;
		if(child < length){
			//判断左右结点哪个值比较大
			if(child < length - 1 && array[child] < array[child + 1]){
				child = child + 1;
			}
			//如果较大值大于根节点的值，那么就进行交换
			if(array[child] > array[i]){
				MaoPaoSort.swap(array, i, child);
				heapAdjustTest(array, child, length);
			}
		}
	}
}
